package LeetCode;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class LC_017_LetterCombinationsofaPhoneNumber {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String s = sc.nextLine();
            List<String> list = new Solution().letterConbinations(s);
            System.out.println(list.toString());
        }
        sc.close();

    }

    static class Solution {
        private final String[] MAP = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

        private List<String> letterConbinations(String num) {
            if (num == null || num.length() == 0)
                return new ArrayList<>();

            ArrayList<String> res = new ArrayList<>();
            dfs("", num, 0, res);
            return res;
        }

        private void dfs(String prefix, String num, int offset, ArrayList<String> res) {
            if (offset == num.length())
                res.add(prefix);
            else {
                String s = MAP[num.charAt(offset) - '0'];
                for (int i = 0; i < s.length(); i++)
                    dfs(prefix + s.charAt(i), num, offset + 1, res);
            }
        }
    }
}


